/*
 * Creator: Eli Viertel
 * 
 * Permission to use: 
 *    Whatever is in the Eclipse Public license and
 *    if not covered there, before using in a paper or in intellectual property
 *    of any other kind (open source or not), 
 *    proper credit must be given to the papers checked in with this code,
 *    especially Brodal and Okasaki.
 *    Also original ideas are presented in code and comments (and eventually a
 *    README -- if not a full-blown paper).
 *    Those ideas must be properly sited as well.
 *    Thanks.
 */

package persistent_heap;

import persistent_heap.internals.LinkedHeap;

/* key point is that everything that would normally change data is, instead,
 * a function that returns a new object representing the change.
 * 
 * minData()/minPri() were always queries, so they just returns the answer
 * like always.
 * 
 * We go from a command-query paradigm to a query-query paradigm.
 * 
 * The garbage collector is the only thing that worries about being destructive
 * ... queued by the user's lack of interest.
 * 
 */

public class PersistentHeap<O, P extends Comparable<? super P>>
{
   // caching min value outside innerHeap makes minData()/minPri() work in
   // constant time vice having to traverse linked list of forest roots
   //
   // OP stands for Object and Priority
   OP _minVal = null;
   
   class OP implements Comparable<OP>
   {
      O _userData;
      P _pri;
      
      private Integer _Id;
      
      OP(O o,  P priority)
      {
         _userData = o;
         _pri = priority;
         _Id = _userData.hashCode();
      }
      
      public int compareTo(OP rhs)
      {
         int comp = _pri.compareTo(rhs._pri);
         return comp == 0 ? _Id.compareTo(rhs._Id) : comp;
      }
   }
   
   LinkedHeap<OP> innerHeap = null;
   
   // TODO: for changeVal() and deleteVal(), could be faster and more memory
   //       efficient to use a HashMap mapping LinkedHeap nodes
   //       to reference count.  As long as inserts are lightning fast,
   //       there would be two advantages:
   //       1) when changeKey() is an increase we might have the option
   //          of actually linking in the change (Hashmap of objects to prev
   //          elements).
   //       2) in the presence of many dup stale values, memory would be saved
   //
   // TODO: Another bell/whistle for size and speed:  Since we are leveraging 
   //       identity <--> equality, can we switch our LinkedHeap,
   //       to also store a reference count?  Whenever we encounter
   //       nodes that equate during stitching, we can bump the count in a copy
   //       of that node, stitching around the old one, for our new patron.
   PersistentHeap<O, P> staleHeap = null;
   
   public PersistentHeap() {}
   
   private PersistentHeap(OP minVal,
                          LinkedHeap<OP> linkedHeap,
                          PersistentHeap<O, P> staleHeap)
   {
      this._minVal = minVal;
      this.innerHeap = linkedHeap;
      this.staleHeap = staleHeap;
   }
   
   public Boolean isEmpty()
   {
      return _minVal == null;
   }
   
   public PersistentHeap<O, P> insert(O userData, P pri)
   {
      OP newOP = new OP(userData, pri);
      
      if (isEmpty())
         return new PersistentHeap<O, P>(newOP, null, new PersistentHeap<O, P>());
      
      if (newOP.compareTo(_minVal) <= 0)
      {
         return new PersistentHeap<O, P>(
               newOP,
            innerHeap == null ? new LinkedHeap<OP>(_minVal) : innerHeap.insert(_minVal),
            staleHeap);
      }
      
      return new PersistentHeap<O, P>(
         _minVal, 
         innerHeap == null ? new LinkedHeap<OP>(newOP) : innerHeap.insert(newOP),
         staleHeap);
   }
   
   // prune parts of the heap that contain priorities greater than maxOk
   public PersistentHeap<O, P> cutGreater(P maxOk)
   {
      if (maxOk.compareTo(_minVal._pri) < 1)
         return new PersistentHeap<O, P>();
      
      return null;
   }
   
   public PersistentHeap<O, P> changeVal(O userData, P oldPri, P newPri)
   {
      if (isEmpty())
      {
         throw new IllegalStateException("nothing to delete");
      }
      
      // guarantees that findMin() is a legal value
      if (oldPri.compareTo(_minVal._pri) == 0)
      {
         if (newPri.compareTo(_minVal._pri) <= 0 || innerHeap == null)
         {
            return new PersistentHeap<O, P>(new OP(userData, newPri), innerHeap, staleHeap);
         }
        
         // else not an O(1) operation.
         return deleteMin().insert(userData, newPri);
      }
      
      // this is O(1), but causes deleteMin() to pay for it
      PersistentHeap<O, P> retHeap = insert(userData, newPri);
      retHeap.staleHeap = staleHeap.insert(userData, oldPri);
      return retHeap;
   }
   
   // Still sometimes grows staleHeap, but always O(logn) or more
   // as it tries to pay for other operations.
   // Remember, though, that in a functional setting, if one client
   // pays for the work, others need to get a new state that reflects
   // the cleanup.  Otherwise they will pay for the work again.
   public PersistentHeap<O, P> eagerDelete(O userData, P currPri)
   {
      if (isEmpty())
      {
         throw new IllegalStateException("nothing to delete");
      }
      
      OP minOP = new OP(_minVal._userData, _minVal._pri);
      
      // should be ok even if someone hashes to this.
      minOP._Id = Integer.MIN_VALUE;
      
      return (new PersistentHeap<O, P>(
            minOP,
            innerHeap.insert(_minVal),
            staleHeap.insert(userData, currPri))).deleteMin();
   }
   
   // Constant time, unless val is the minimum.
   public PersistentHeap<O, P> lazyDelete(O userData, P currPri)
   {
      if (isEmpty())
      {
         throw new IllegalStateException("nothing to delete");
      }
      
      // TODO: Should even this case be lazy?
      if (userData.equals(_minVal._userData)
            && currPri.compareTo(_minVal._pri) == 0)
      {
         // do the O(logn) now rather than 2 x O(logn) later
         return deleteMin();
      }
      
      // O(1).  But then longer deleteMin() time cleaning up
      return new PersistentHeap<O, P>(
            _minVal, innerHeap, staleHeap.insert(userData, currPri));
   }
   
   // O(logn), but non-trivial constant. longer real
   // time than internal findMin() or internal meld()
   public PersistentHeap<O, P> deleteMin()
   {
      if (isEmpty())
      {
         throw new IllegalStateException("nothing to delete");
      }
      
      if (innerHeap != null)
      {
         OP newMinVal = innerHeap.findMin().value;
         
         // this is where "everyone" (amortization breaks down in FP)
         // with this version may pay for some changeVal()'s
         LinkedHeap<OP> newInnerHeap = innerHeap;
         PersistentHeap<O, P> newStaleHeap = staleHeap;
         
         while (!newStaleHeap.isEmpty()
                && newStaleHeap._minVal._pri.compareTo(newMinVal._pri) == 0
                && newStaleHeap._minVal._userData.equals(newMinVal._userData)
                && newInnerHeap != null)
         {
            newInnerHeap = newInnerHeap.deleteMin();
            newStaleHeap = newStaleHeap.deleteMin();
            
            if (newInnerHeap != null)
            {
               newMinVal = newInnerHeap.findMin().value;
            }
            else
            {
               // TODO: 
               //   One speedup could be to track the max real val.
               //   (Do we would need a max heap for this, or
               //   can we maintain max at each node and bubble up aswer at
               //   every link?)
               //
               //   Anyway, if we are ever starting look at vals > max,
               //   the rest is all junk.  Stop the 'while' before
               //   newInnerHeap is null. throw it all away.
               //   It would be nice to do this at the time of changeVal().
               //   We can't, tho.  We can't skip the insert into staleHeap
               //   for oldVal's > max because someone could changeVal() above
               //   max with a real val.  Then all those lesser bogus vals
               //   would look real because we weren't tracking them.
               //
               //   This also supports stitching together cutGreater()
               return new PersistentHeap<O, P>();
            }
         }
         
         if (newInnerHeap != null)
         {
            return new PersistentHeap<O, P>(
                  newMinVal,
                  newInnerHeap.deleteMin(),
                  newStaleHeap);
         }
         
         return new PersistentHeap<O, P>(newMinVal, null, null);
      }

      return new PersistentHeap<O, P>();
   }

   public O minData()
   {
      return _minVal._userData;
   }
   
   public P minPri()
   {
      return _minVal._pri;
   }

   public PersistentHeap<O, P> meld(PersistentHeap<O, P> otherHeap)
   {
      if (isEmpty())
         return otherHeap;
      
      if (otherHeap.isEmpty())
         return this;

      if (_minVal.compareTo(otherHeap._minVal) < 0)
      {
         if (innerHeap == null)
         {
            return new PersistentHeap<O, P>(
                  _minVal,
                  otherHeap.innerHeap.insert(otherHeap._minVal),
                  staleHeap);
         }
         if (otherHeap.innerHeap == null)
         {
            return new PersistentHeap<O, P>(
                  _minVal,
                  innerHeap.insert(otherHeap._minVal),
                  staleHeap);
         }
         return new PersistentHeap<O, P>(
               _minVal,
               innerHeap.meld(otherHeap.innerHeap).insert(otherHeap._minVal),
               staleHeap);
      }

      if (innerHeap == null)
      {
         return new PersistentHeap<O, P>(
               otherHeap._minVal,
               otherHeap.innerHeap.insert(_minVal),
               staleHeap);
      }
      if (otherHeap.innerHeap == null)
      {
         return new PersistentHeap<O, P>(
               otherHeap._minVal,
               innerHeap.insert(_minVal),
               staleHeap);
      }
      return new PersistentHeap<O, P>(
            otherHeap._minVal,
            otherHeap.innerHeap.meld(innerHeap).insert(_minVal),
            staleHeap);
   }
}